import java.util.*;

public class PartitionQuickSort {

    public static void main(String[] args) {
        Random rand = new Random();
//        System.out.println();
//        PartitionQuickSort quickSort = new PartitionQuickSort();
        System.out.println(new Random().nextInt(1, 4));
        System.out.println();
//        quickSort.sortArray(new int[]{5, 2, 3, 1});
        int[] i = new int[10];
        List<Integer> list = new ArrayList<>(10);
    }


    /**
     * 翻转对
     */
    int[] tmp;
    public int reversePairs1(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return getCountReversePairs(nums, 0, n-1);
    }

    int getCountReversePairs(int[] nums, int left, int right){
        if(left == right) return 0;

        int mid = (left + right) / 2;

        int a = getCountReversePairs(nums, left, mid);
        int b = getCountReversePairs(nums, mid + 1, right);

        //获取到翻转对个数 降序排列的
        int c = 0;

        int cur1 = left, cur2 = mid + 1, i = 0;
        //while 会比for 快一点
        while(cur1 <= mid){
            while(cur2 <= right && nums[cur1] / 2.0 <=  nums[cur2]) cur2++;
            c += right - cur2 + 1;
            if(cur2 > right) break;
            cur1++;
        }

        //排序
        cur1 = left; cur2 = mid + 1; i = 0;
        for(;cur1 <= mid && cur2 <= right;){
            tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(i = left; i <= right; i++){
            nums[i] = tmp[i-left];
        }

        return a + b + c;
    }
    /**
     * 计算右侧小于当前元素的个数
     * 整体的和找逆序对差不多 唯一的区域别是在排完序之后 元素的位置变了，而他又是放回需要原来的元素的位置
     * 那么就使用了一个indexs来记录下每个元素的原来的位置 这样就课以在排序的时候顺便把值也给找了
     */
    int[] counts;
    int[] tmp1;
    int[] indexs;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        counts = new int[n];
        tmp = new int[n];
        indexs = new int[n];
        tmp1 = new int[n];
        for(int i  = 0; i < n;i++){
            indexs[i] = i;
        }
        mergeCount(nums, 0, n - 1);
        List<Integer> ret = new LinkedList<>();
        for (int i : counts)
            ret.add(i);
        return ret;
    }


    //over time  需要记录下每个元素的原始下标 使用在排序后找时就可以将值放到原始的那个位置 这样就是nlog(n)
    void mergeCount(int[] nums, int left, int right) {
        if (left >= right)
            return;

        int mid = (left + right) / 2;

        //找到右边区间的
        mergeCount(nums, mid + 1, right);
        //计算个数
        getCount(nums, left, right, mid);
        //找到左边区间的
        mergeCount(nums, left, mid);
        //排序
        sort(nums, left, right, mid);
    }
    void getCountPass (int[] nums, int left, int right, int mid){
        //将左边的和右边的小于的结合 这时他们是逆序排序的
        //俩边排序逆序
        int cur1 = left;int cur2 = mid+1; int i = 0;
        for(; cur1 <= mid && cur2 <= right;){
            if(nums[cur1]> nums[cur2]){
                tmp1[i] = indexs[cur1];//记录下标
                tmp[i++] = nums[cur1];
                //跟新取值
                counts[indexs[cur1++]] += right - cur2 + 1;
            }else{
                tmp1[i] = indexs[cur2];
                tmp[i++] = nums[cur2++];
            }
        }

        while(cur1 <= mid) {
            tmp1[i] = indexs[cur1];;//记录下标
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= right){
            tmp1[i] = indexs[cur2];;
            tmp[i++] = nums[cur2++];
        }

        for(int j = left; j <= right; j++){
            nums[j] = tmp[j-left];
            indexs[j] = tmp1[j-left];
        }
    }
    void getCount(int[] nums, int left, int right, int mid) {
        //将左边的和右边的小于的结合 这时他们是逆序排序的
        int cur1 = left, cur2 = mid + 1;
        for (; cur1 <= mid; cur1++) {
            int count = 0;
            for (cur2 = mid + 1; cur2 <= right; cur2++) {
                if (nums[cur1] > nums[cur2]) {
                    count += right - cur2 + 1;
                    break;
                }
            }
            counts[cur1] += count;
        }

    }

    //相同的数的优化
    void sort(int[] nums, int left, int right, int mid) {
        //排序错了
        //俩边排序逆序
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;

        for (; cur1 <= mid && cur2 <= right;) {
            tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while (cur2 <= right)
            tmp[i++] = nums[cur2++];
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }

    }


    /**
     * 交易逆序对的总数
     * 有一种想法是 把数组分为俩半 先找左边的逆序对 再到右边的逆序对 在找左右俩边的逆序对
     * 而左边的又可以再分为俩半 这样就和归并很切合了
     * 为了更快的找出左右俩边的逆序对，那么就可以将他们排序 这就和归并更像了
     * 所以是使用归并的思想解决
     */
    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        return mergePairs(record,0,record.length-1);
    }

    int mergePairs(int[] record, int l, int r){
        if(l>=r) return 0;

        int mid = (l + r) / 2;

        //左遍历 得到左边的逆序数
        int a =  mergePairs(record,l,mid);
        //右边遍历
        int b = mergePairs(record,mid+1,r);

        //对左右排序 并且得到左边和右边的逆序数
        int c = 0, cur1 = l, cur2 = mid+1, i = 0;
        for(;cur1<=mid && cur2<=r;){
            if(record[cur1] > record[cur2]){
                tmp[i++] = record[cur2++];
                //说明cur1后面的都大于cur2 这些都是逆序对
                c += mid - cur1 + 1;
            }else{
                tmp[i++] = record[cur1++];
            }
        }

        while(cur1<=mid) tmp[i++] = record[cur1++];
        while(cur2<=r) tmp[i++] = record[cur2++];
        //合并
        for(int j = l; j <= r; j++){
            record[j] = tmp[j-l];
        }

        return a+b+c;
    }

    /**
     * 最小的K个数
     */
    public int[] smallestK(int[] arr, int k) {
        int n = arr.length;
        recursionSmallestK(arr,0,n-1,k);
        int[] ret = new int[k];
        for(int i = 0; i < k; i++){
            ret[i] = arr[i];
        }
        return ret;
    }

    void recursionSmallestK(int[] arr, int start, int end, int k){
        if(start >= end) return;

        int key = arr[new Random().nextInt(end-start) + start];

        int l = start - 1, r = end + 1;

        for(int i = start; i <= end && i < r;){
            if(arr[i] < key) swap(arr, ++l, i++);
            else if(arr[i] > key) swap(arr, --r, i);
            else i++;
        }

        // s,l   l+1,r-1  r,e
        int a = l - start + 1, b = r - l - 1;
        if(a > k) recursionSmallestK(arr, start, l, k);
        else if(a + b >= k) return;
        else recursionSmallestK(arr, r, end, k - a - b);
    }
    /**
     * 数组中的第K个最大元素
     * 将数字分为三份
     */
    int RetFindKthLargest = 0;

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        recursionFindKthLargest(nums, 0, n - 1, k);
        return RetFindKthLargest;
    }

    void recursionFindKthLargest(int[] nums, int start, int end, int k) {
        if (start >= end) {
            RetFindKthLargest = nums[start];
            return;
        }

        int key = nums[new Random().nextInt(end - start) + start];
        int l = start - 1, r = end + 1, n = nums.length;

        for (int i = start; i <= end && i < r;) {
            if (nums[i] < key)
                swap(nums, ++l, i++);
            else if (nums[i] > key)
                swap(nums, --r, i);
            else
                i++;
        }

        //元素个数 [s l] [l+1,r-1] [r,end]
        int b = r - l - 1, c = end - r + 1;
        if (c >= k)
            recursionFindKthLargest(nums, r, end, k);
        else if (b + c >= k)
            RetFindKthLargest = key;
        else
            recursionFindKthLargest(nums, start, l, k - b - c);
    }

    /**
     *  排序数组
     *  分为三部分来排序 快速排序 nlog(n)
     */

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        recursionSortArray(nums, 0, n - 1);
        mergeSort(nums, 0, n - 1);
        return nums;
    }

    //归并排序

    int[] tmpArray;
    void mergeSort(int[] nums, int left, int right){
        if(left >= right) return;

        //分俩半
        int mid = (left+right)/2;

        //将这俩半分别排序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        //合并俩个有序数组排序 l mid , mid+1 r
        int cur1 = left, cur2 = mid+1, i = 0;

        for(; cur1 <= mid &&cur2 <= right; i++){
            tmpArray[i] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        while(cur1 <= mid) tmpArray[i++] = nums[cur1++];
        while(cur2 <= right) tmpArray[i++] = nums[cur2++];

        //将tmp放回nums中
        for(int j = left; j <= right; j++){
            nums[j] = tmpArray[j-left];
        }
    }

    //分三个部分排序 [l,r]
    void recursionSortArray(int[] nums, int start, int end) {
        if (start >= end)
            return;
        int key = nums[start + new Random().nextInt(end - start)];
        int left = start - 1, right = end + 1;

        for (int i = start; i <= end && i < right;) {
            if (nums[i] < key)
                swap(nums, ++left, i++);
            else if (nums[i] > key)
                swap(nums, --right, i);
            else
                i++;
        }

        recursionSortArray(nums, start, left);
        recursionSortArray(nums, right, end);
    }

    /**
     * 颜色归类
     */
    public void sortColors(int[] nums) {
        int n = nums.length;
        int l = -1, r = n;
        for(int i = 0; i < n&&i<r;){
            if(nums[i] == 0){
                swap(nums,++l,i++);
            }else if(nums[i] == 2){
                swap(nums,--r,i);
            }else{
                i++;
            }
        }
    }
    void swap(int[] nums,int i,int j){
        int r = nums[i];
        nums[i] = nums[j];
        nums[j] = r;
    }
}
